<?php
/**
 * 题目链接 https://leetcode.cn/problems/valid-parentheses/description/
 */

class Solution {

    /**
     * 利用栈
     * @param String $s
     * @return Boolean
     */
    public static function isValid(string $s): bool 
    {
        $left_map  = ['(' => 0, '[' => 1, '{' => 2];
        $right_map = [')' => 0, ']' => 1, '}' => 2];

        $len = strlen($s);
        $left = [];

        for ($i=0; $i < $len; $i++) { 
            if (isset($left_map[$s[$i]])) {
                $left[] = $s[$i];
            } else {
                if ($i < 1) {
                    return false;
                }
                $l = array_pop($left);
                if ($l == null || $right_map[$s[$i]] != $left_map[$l]) {
                    return false;
                }
            }
        }

        return empty($left);
    }

}

$test = [
    ["["],
    ["()"],
    ["()[]{}"],
    ["(]"],
    ["[])"],
];
$result = [
    false, true, true, false, false
];

foreach ($test as $key => $value) {
    $r = Solution::isValid($value[0]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    var_dump($r);
}